# 下一个排列： https://leetcode-cn.com/problems/next-permutation/
# 此题为 腾讯面试题。2021年春招


class Solution:
    def nextPermutation(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        字典序： 也就是序列全部的排列组合
        下一个更大的： 比如 [1,2,3]（123） 下一个更大的就是 [1,3,2]（132）
        """

        """
        解题思路：直接模拟过程，寻找算法规律
        1. 首先需要从后往前找， 因为 位数是  (... 万千百十个)这样子的， 要从个位往上找（从右向左）
        2. 以 123(最小的数)为例。  逆着找 3（个位） > 2 十位 ，则直接进行交换 132 就是最小的
        3. 132, 逆着找（右向左）,  1（百位） < 3(十位) 则 进行交换  这时候需要用 十位，个位当中最小的替换，就成了231
        4. 231 显然不是最接近 132的, 需要将 十位，个位逆序。因为 第三步中间判断到 1（百位了），说明 个位 < 十位（2 < 3）, 百位 < 十位（1 < 3）, 所以将剩下的 十位，各位逆序，才能是最小的。 变成 213
        5. 此时 213. 逆着找 1 小于 3， 那就直接 变为 2 31
        6. 此时 231. 逆着找 2 小于 3，需要寻找 比2 大一点的数（最接近2的）  变为 321， 然后 反转312
        7. 312 变为 321
        8. 321 是最大的了， 低位比高位大的。 所以全部反转 123

        # 尝试 452631
        1. 首先找到低位比高位大的 2 6
        2. 从 2 后面调出来 最接近2的，需要大于2. 也就是3， 交换变为 453621 
        3. 低位的数字逆序 变为 453126（为什么能直接逆序后面的数字，因为既然选择到2 6，和3 ，2 一定 大于等于3之后的数，如果不大于，那就选择3之后的数了）
        """

        def reverse(low, high):
            """ 用来进行反转 """
            while low < high:
                nums[low], nums[high] = nums[high], nums[low]
                low, high = low + 1, high - 1

        # 写代码实现
        n = len(nums)
        for i in range(n-1, 0, -1):      
            # 如果高位小于低位数字
            if nums[i-1] < nums[i]:
                # 完成 高位 与最接近且大于它的低位进行交换, 最接近的低位，一定是逆序遍历大于它的第一个数
                for j in range(n-1, 0, -1):
                    if nums[j] > nums[i-1]:
                        nums[i-1], nums[j] = nums[j], nums[i-1]
                        break
                # 再将高位往后的低位进行逆序
                reverse(i, n-1)
                break
        else:
            # 正常循环结束，则说明是最大的直接反转
            reverse(0, n-1)


nums = [3, 2, 1]
s = Solution()
a = s.nextPermutation(nums)
print(a)
